﻿/*142. 前缀统计

给定 N个字符串 S1,S2…SN，接下来进行 M次询问，每次询问给定一个字符串 T，求 S1∼SN中有多少个字符串是 T的前缀。
输入字符串的总长度不超过 106，仅包含小写字母。

输入格式
第一行输入两个整数 N，M
接下来 N行每行输入一个字符串 Si
接下来 M行每行一个字符串 T用以询问。

输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。

数据范围
1≤N,M≤105
输入样例：
3 2
ab
bc
abc
abc
efg
输出样例：
2
0
解释：分别在2个数看，3个是不是前缀，比如abc那么ab,abc都是前缀，但是bc不是*/

#include<iostream>
using namespace std;
const int N = 100010, M = 500000;
//N行每行输入一个字符串 Si
//接下来 M行每行一个字符串 T用以询问
int n, m;
int son[N][26], cnt[N], idx;
char str[N];

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        //int u=str[i]-'a';
        //if(!son[p][str[i]-'a']) son[p][str[i]-'a']=idx++;
        int& s = son[p][str[i] - 'a'];
        if (!s)  s = ++idx;//定义的时候&s=数组，s在使用的时候就代表该数组
        p = s;
    }
    cnt[p]++;
}
int query()
{
    int p = 0;
    int res = 0;
    for (int i = 0; str[i]; i++)
    {
        int& s = son[p][str[i] - 'a'];
        if (!s) break;
        p = s;
        res += cnt[p];
        //前缀和这个计算是把这条路到节点都累加上
    }
    //return cnt[p];这个是计算字符串出现的次数
    return res;
}
int main()
{
    int n, m;
    cin >> n >> m;//输入顺序
    while (n--)
    {
        cin >> str;
        insert();
    }
    //int m;
    //cin>>m;
    while (m--)
    {
        cin >> str;
        cout << query() << endl;
    }
}
/*
1.注意输入的顺序
2.和teri树的区别在于前缀和计算的该路上面所有前缀累加，res += cnt[p];
先对N个树插入建成树，然后对待查前缀的M数query()查询
3.对于scanf和cin,大于100 0000 scanf()保险一点，会快
4.int son[N][26],cnt[N]也可以用结构体实现：
struct Node{
    int son[26];
    int cnt;
};*/